{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 120. 三角形最小路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "[\n",
    "     [2],\n",
    "    [3,4],\n",
    "   [6,5,7],\n",
    "  [4,1,8,3]\n",
    "]\n",
    "自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/triangle\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用深度搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        min_res = float(\"inf\")\n",
    "        height = len(triangle)\n",
    "        if height == 0:\n",
    "            return 0\n",
    "        if height == 1:  # 在triangle为1长度时候报错了\n",
    "            return triangle[0][0]\n",
    "        # 当前的层数,当前的索引\n",
    "        def helper(n, index, res):\n",
    "            nonlocal min_res\n",
    "            if n == height-1:\n",
    "                min_res = min(min_res, res + triangle[n][index], res + triangle[n][index+1])\n",
    "                return\n",
    "            for i in range(2):\n",
    "                print(n, index+i, res)\n",
    "                helper(n+1, index+i, res+triangle[n][index+i])\n",
    "                if n == index+i:\n",
    "                    break\n",
    "        helper(0, 0, 0)\n",
    "        return min_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 0\n",
      "1 0 2\n",
      "2 0 5\n",
      "2 1 5\n",
      "1 1 2\n",
      "2 1 6\n",
      "2 2 6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Solution().minimumTotal([\n",
    "     [2],\n",
    "    [3,4],\n",
    "   [6,5,7],\n",
    "  [4,1,8,3]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 0\n",
      "1 0 2\n",
      "2 0 5\n",
      "2 1 5\n",
      "1 1 2\n",
      "2 1 6\n",
      "2 2 6\n"
     ]
    }
   ],
   "source": [
    "s1 =  [\n",
    "     [2],\n",
    "    [3,4],\n",
    "   [6,5,7],\n",
    "  [4,1,8,3]\n",
    "]\n",
    "assert Solution().minimumTotal(s1) ==  11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 0\n"
     ]
    }
   ],
   "source": [
    "s2 = [\n",
    "    [1],\n",
    "    [2, 3]\n",
    "]\n",
    "assert Solution().minimumTotal(s2) == 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "s3 = [[-10]]\n",
    "assert Solution().minimumTotal(s3) == -10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在运行 `[[46],[43,61],[10,-16,3],[-26,41,36,-72],[-28,-76,-22,26,51],[56,-53,38,67,86,-45],[58,53,47,-52,-54,-95,56],[-54,-93,58,68,26,-4,-45,86],[75,28,27,12,33,98,35,87,1],[-13,20,25,-98,-13,11,-44,-77,-59,-97],[-53,-14,83,80,31,89,38,-1,15,-88,53],[-22,86,-41,-94,-25,68,-96,87,55,-18,-49,-25],[-93,-48,39,17,8,61,57,-13,-92,-79,-29,87,51],[-63,3,-72,29,-9,57,-93,-46,-84,88,29,83,69,-7],[15,-49,43,90,-43,94,29,50,-21,-33,-16,43,-26,4,90],[-61,-67,-96,18,-63,32,-91,93,16,-61,86,4,67,46,-27,-63],[-38,0,79,-48,56,51,80,-17,-70,-53,67,49,-3,-52,39,12,-43],[43,-93,-7,-48,91,-13,44,-69,-27,-74,74,95,-25,-88,-43,75,90,8],[8,41,-35,91,48,-12,35,-3,62,59,-86,-49,-83,56,-42,-14,84,-74,72],[6,-44,-78,31,-92,-82,-94,-81,-49,57,85,36,-34,4,77,-66,-71,-34,45,25],[-95,4,15,-45,-3,-52,-11,83,-67,15,32,38,47,54,-54,54,48,-72,72,75,85],[35,11,-72,-61,-11,-62,-33,31,82,68,35,-37,-16,66,37,31,-44,20,40,47,-71,-45],[-6,59,0,-51,7,5,97,-40,-10,32,70,-6,47,-41,31,-86,89,-10,59,1,29,-57,-32],[-34,73,0,62,-9,-53,91,4\n",
    "...`的时候超出时间限制了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义dp数组\n",
    "\n",
    "dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        height = len(triangle)\n",
    "        if height == 0:\n",
    "            return 0\n",
    "        dp = [0] * height\n",
    "        dp[0] = triangle[0][0]\n",
    "        for i in range(1, height):\n",
    "            tmp = dp.copy()\n",
    "            for j in range(i+1):\n",
    "                if j == 0: # 最左边的\n",
    "                    dp[0] = tmp[0] + triangle[i][j]\n",
    "                elif j == i: # 最右边的\n",
    "                    dp[j] = tmp[j-1] + triangle[i][j]\n",
    "                else: # 中间的\n",
    "                    dp[j] = min(triangle[i][j] + tmp[j], triangle[i][j] + tmp[j-1])\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "=0\n",
      "1\n",
      "[5, 6, 0, 0]\n",
      "0\n",
      "=0\n",
      "1\n",
      "2\n",
      "[11, 10, 13, 0]\n",
      "0\n",
      "=0\n",
      "1\n",
      "2\n",
      "3\n",
      "[15, 11, 18, 16]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Solution().minimumTotal(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "=0\n",
      "1\n",
      "[3, 4]\n"
     ]
    }
   ],
   "source": [
    "assert Solution().minimumTotal(s2) == 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert Solution().minimumTotal(s3) == -10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
